package com.wrial.kind.dp;
/*
 * @Author  Wrial
 * @Date Created in 17:42 2020/8/8
 * @Description
 * 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
 */

public class MaxProfit {
    /**
     * 动态规划：dp[i] = Max(dp[i-1],prices[i]-prices[min])
     *
     * @param prices
     * @return
     */
//    public int maxProfit(int[] prices) {
//        if (prices == null || prices.length <= 1) return 0;
//        int min = prices[0];
//        int[] dp = new int[prices.length];
//        dp[0] = 0;
//        for (int i = 1; i < dp.length; i++) {
//            dp[i] = Math.max(dp[i - 1], prices[i] - min);
//            min = Math.min(min, prices[i]);
//        }
//        return dp[prices.length - 1];
//    }

    /**
     * 改进版，不需要动态规划数组
     * @param prices
     * @return
     */
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;
        int min = prices[0];
        int ans = 0;
        for (int i = 1; i < prices.length; i++) {
            ans = Math.max(ans, prices[i] - min);
            min = Math.min(min, prices[i]);
        }
        return ans;
    }
}
